<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML>
<HEAD>
	<META HTTP-EQUIV="CONTENT-TYPE" CONTENT="text/html; charset=windows-1252">
	<TITLE></TITLE>
	<META NAME="GENERATOR" CONTENT="BrOffice.org 2.4  (Win32)">
	<META NAME="AUTHOR" CONTENT="Karina Kieling">
	<META NAME="CREATED" CONTENT="20080929;60500">
	<META NAME="CHANGEDBY" CONTENT="Karina Kieling">
	<META NAME="CHANGED" CONTENT="20081101;21515379">
	<STYLE TYPE="text/css">
	<!--
		@page { margin: 2cm }
		P { margin-bottom: 0.21cm }
		P.western { so-language: pt-BR }
		P.lista-western { so-language: pt-BR }
		P.lista-ctl { font-family: "Tahoma" }
	-->
	</STYLE>
</HEAD>
<BODY LANG="pt-BR" DIR="LTR">
<P STYLE="margin-bottom: 0cm; line-height: 150%"></P>
<P STYLE="margin-bottom: 0cm; line-height: 150%"></P>
<P STYLE="margin-bottom: 0cm; line-height: 150%"><B>EXPRESS&Otilde;ES
REGULARES</B></P>
<P CLASS="western"><BR><BR>
</P>
<P CLASS="western" STYLE="line-height: 150%">	Cada express&atilde;o
regular <I>r</I> denota uma <A HREF="conceitos%20basicos.html">linguagem</A>
L (<I>r</I>), onde as regras de defini&ccedil;&atilde;o especificam
como a linguagem &eacute; formada atrav&eacute;s da combina&ccedil;&atilde;o,
em varias formas, das linguagens denotadas pelas subexpress&otilde;es
de<I> r</I> (AHO; SETHI; ULLMANN, 1995). 
</P>
<P CLASS="western" STYLE="line-height: 150%">	A representa&ccedil;&atilde;o
da linguagem L (r) pode ser definida a partir de express&otilde;es
b&aacute;sicas como (PRICE; TOSCANI, 2001):</P>
<OL>
	<LI><P CLASS="lista-western" STYLE="line-height: 150%"><FONT FACE="Tahoma, sans-serif">&Oslash;</FONT>
	representa a linguagem vazia (conjunto contendo zero palavra);</P>
	<LI><P CLASS="lista-western" STYLE="line-height: 150%">{<FONT FACE="Symbol, serif">&#61541;&#61565;</FONT><FONT FACE="Times New Roman, serif">
	representa a linguagem cuja &uacute;nica palavras &eacute; a vazia;</FONT></P>
	<LI><P CLASS="lista-western" STYLE="line-height: 150%"><FONT FACE="Times New Roman, serif">{
	x | x </FONT><FONT FACE="Symbol, serif">&#61646;&#61472;&#61524;&#61565;&#61472;</FONT><FONT FACE="Times New Roman, serif">representa
	a linguagem cuja &uacute;nica palavras &eacute; x;</FONT></P>
	<LI><P CLASS="lista-western" STYLE="line-height: 150%">se r<FONT SIZE=1 STYLE="font-size: 6pt">1</FONT>
	| r<FONT SIZE=1 STYLE="font-size: 6pt">2</FONT> s&atilde;o
	express&otilde;es regulares definindo as linguagens L (r<FONT SIZE=1 STYLE="font-size: 6pt">1</FONT>)
	e L (r<FONT SIZE=1 STYLE="font-size: 6pt">2</FONT>), tem-se que:</P>
</OL>
<OL>
	<OL TYPE=a>
		<LI><P CLASS="lista-western" STYLE="line-height: 150%"><FONT FACE="Times New Roman, serif">r</FONT><FONT FACE="Times New Roman, serif"><FONT SIZE=1 STYLE="font-size: 6pt">1</FONT></FONT><FONT FACE="Times New Roman, serif">
		| r</FONT><FONT FACE="Times New Roman, serif"><FONT SIZE=1 STYLE="font-size: 6pt">2</FONT></FONT><FONT FACE="Times New Roman, serif">
		&eacute; a linguagem cujas palavras constituem o conjunto L (r</FONT><FONT FACE="Times New Roman, serif"><FONT SIZE=1 STYLE="font-size: 6pt">1</FONT></FONT><FONT FACE="Times New Roman, serif">)
		</FONT><FONT FACE="Symbol, serif">&#61640;</FONT><FONT FACE="Times New Roman, serif">
		L (r</FONT><FONT FACE="Times New Roman, serif"><FONT SIZE=1 STYLE="font-size: 6pt">2</FONT></FONT><FONT FACE="Times New Roman, serif">);</FONT></P>
		<LI><P CLASS="lista-western" STYLE="line-height: 150%"><FONT FACE="Times New Roman, serif">r</FONT><FONT FACE="Times New Roman, serif"><FONT SIZE=1 STYLE="font-size: 6pt">1</FONT></FONT><FONT FACE="Times New Roman, serif">
		r</FONT><FONT FACE="Times New Roman, serif"><FONT SIZE=1 STYLE="font-size: 6pt">2</FONT></FONT><FONT FACE="Times New Roman, serif">
		&eacute; a linguagem { vw | v </FONT><FONT FACE="Symbol, serif">&#61646;&#61472;</FONT><FONT FACE="Times New Roman, serif">L
		(r</FONT><FONT FACE="Times New Roman, serif"><FONT SIZE=1 STYLE="font-size: 6pt">1</FONT></FONT><FONT FACE="Times New Roman, serif">)
		e w </FONT><FONT FACE="Symbol, serif">&#61646;&#61472;</FONT><FONT FACE="Times New Roman, serif">L
		(r</FONT><FONT FACE="Times New Roman, serif"><FONT SIZE=1 STYLE="font-size: 6pt">2</FONT></FONT><FONT FACE="Times New Roman, serif">),
		isto &eacute;, a linguagem cujas palavras s&atilde;o formadas pela
		concatena&ccedil;&atilde;o de uma palavra de L(r</FONT><FONT FACE="Times New Roman, serif"><FONT SIZE=1 STYLE="font-size: 6pt">1</FONT></FONT><FONT FACE="Times New Roman, serif">)
		com uma palavras de L(r</FONT><FONT FACE="Times New Roman, serif"><FONT SIZE=1 STYLE="font-size: 6pt">2</FONT></FONT><FONT FACE="Times New Roman, serif">),
		nesta ordem;</FONT></P>
		<LI><P CLASS="lista-western" STYLE="line-height: 150%">r<FONT SIZE=1 STYLE="font-size: 6pt">1</FONT>*
		representa o conjunto L*(r<FONT SIZE=1 STYLE="font-size: 6pt">1</FONT>),
		isto &eacute;, o conjunto de palavras que podem ser formadas
		concatenando-se zero ou mais palavras de L(r<FONT SIZE=1 STYLE="font-size: 6pt">1</FONT>).</P>
		<P CLASS="lista-western" STYLE="line-height: 150%"></P>
	</OL>
</OL>
<P CLASS="western" STYLE="line-height: 150%"><FONT FACE="Times New Roman, serif">	Exemplo
de express&otilde;es regulares,  seja </FONT><FONT FACE="Symbol, serif">&#61523;</FONT><FONT FACE="Times New Roman, serif">
= {a, b}(AHO; SETHI; ULLMANN, 1995):</FONT></P>
<OL>
	<LI><P CLASS="lista-western" STYLE="line-height: 150%">a express&atilde;o
	regular a | b significa o conjunto {a,b};</P>
	<LI><P CLASS="lista-western" STYLE="line-height: 150%">a express&atilde;o
	regular  (a | b) (a | b) denota {aa, ab, ba, bb), o conjunto de
	todas as cadeias de a's b's de comprimento dois. Outra express&atilde;o
	regular para esse conjunto &eacute; aa | ab | ba | bb.</P>
	<LI><P CLASS="lista-western" STYLE="line-height: 150%"><FONT FACE="Times New Roman, serif">A
	express&atilde;o regular a* significa o conjunto de todas as cadeias
	de zero ou mais a's, isto &eacute;, {</FONT><FONT FACE="Symbol, serif">&#61541;&#61484;&#61472;</FONT><FONT FACE="Times New Roman, serif">a,
	aa, aaa, ....};</FONT></P>
	<LI><P CLASS="lista-western" STYLE="line-height: 150%"><FONT FACE="Times New Roman, serif">A
	express&atilde;o regular (a | b)* significa o conjunto de todas as
	cadeias contendo zero ou mais inst&acirc;ncias de um </FONT><FONT FACE="Times New Roman, serif"><I>a</I></FONT><FONT FACE="Times New Roman, serif">
	ou um </FONT><FONT FACE="Times New Roman, serif"><I>b, </I></FONT><FONT FACE="Times New Roman, serif">ou
	seja, junto de todas as cadeias a's e b's.</FONT></P>
</OL>
<P CLASS="lista-western" STYLE="line-height: 150%"><BR><BR>
</P>
<P CLASS="western" STYLE="margin-bottom: 0cm; line-height: 150%"><IMG SRC="expressoes_regulares_html_m637a0871.gif" ALIGN=MIDDLE>
<FONT FACE="Times New Roman, serif"><A HREF="Indice.html">Voltar
&Iacute;ndice</A></FONT></P>
<P CLASS="western" STYLE="margin-bottom: 0cm; line-height: 150%"><BR>
</P>
<P CLASS="western" STYLE="margin-bottom: 0cm; line-height: 150%"><BR>
</P>
<P CLASS="western" STYLE="margin-bottom: 0cm; line-height: 150%"><BR>
</P>
<P CLASS="western" STYLE="margin-left: 1.27cm; line-height: 150%"><BR><BR>
</P>
</BODY>
</HTML>